package com.xiaoyu.linkedArray;

import java.util.HashSet;

/**
 * @program: DS_and_A
 * @description: TODO
 * @author: YuWenYi
 * @create: 2021-06-01 10:36
 **/
public class DetectCycle_142 {

    //解法一:使用set简单方便
    public static ListNode detectCycle(ListNode head) {
        HashSet<ListNode> set = new HashSet<>();
        ListNode p = head;

        while (p != null){
            if (set.contains(p)){
                return p;
            }
            set.add(p);
            p = p.next;
        }
        return null;
    }


    //解法二:双指针
    /*
    * 概括一下：
      根据：
        f=2s （快指针每次2步，路程刚好2倍）
        f = s + nb (相遇时，刚好多走了n圈）
        推出：s = nb
        从head结点走到入环点需要走 ： a + nb， 而slow已经走了nb，那么slow再走a步就是入环点了。
        如何知道slow刚好走了a步？ 从head开始，和slow指针一起走，相遇时刚好就是a步
    *
    * */
    public static ListNode detectCycle1(ListNode head) {
        ListNode fast = head;
        ListNode slow = head;

        //快指针走两步,慢指针走一步
        while (true) {
            if (fast == null || fast.next == null) return null;
            fast = fast.next.next;
            slow = slow.next;
            if (fast == slow) break;  //第一次相遇
        }

        fast = head;  //重置fast
        while (fast != slow) {
            fast = fast.next;
            slow = slow.next;
        }
        return slow;
    }


    public static void main(String[] args) {
        ListNode l1 = new ListNode(1,new ListNode(2,
                new ListNode(3,new ListNode(4))));
        //l1.next.next.next.next = l1.next.next;

        ListNode node = detectCycle1(l1);

        System.out.println(node.val);
    }
}
